package com.hsc.offer;

/**
 * @author
 * @date 2025-06-23
 * @Description 15.输入一个链表，反转链表后，输出新链表的表头。
 */
public class OfferTest10 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        ListNode listNode = reverseList(node1);
    }

    public static ListNode reverseList(ListNode head) {
        System.out.println(head.val);
        // 健壮性判断
        // 如果当前链表为null
        if (head == null) {
            return null;
        }
        // 如果当前链表只有一个节点 表头就是自己
        if (head.next == null) {
            return head;
        }
        // 链表正常的清理
        // 因为反正链表 所以我们需要从链表最后一个节点进行反装
        // 链表尾节点就是 新的链表的表头
        // 我们需要找到倒数第二个节点
        // 如果倒数第二个节点的next的next 不为null 说明还没有找到
        if (head.next.next != null) {
            // 继续找到倒数第二节点 递归
            ListNode result = reverseList(head.next); //继续往下找
            System.out.println(result.val);
            // 当递归终止时 会返回倒数第一个节点 作为表头
            // 当前传入的head 传入的还是当前的节点
            // head.next 指向下一个节点
            // head.next.next 是下一个节点的指针
            head.next.next = head; // 这里需要将下一个节点的next 指针指向自己 （当前节点）
            // 还需要将当前节点的next 指针额置null  避免成环
            head.next = null;
            // 返回 出栈
            return result;
        } else {
            System.out.println(head.val);
            // 找到倒数第二个节点  递归的临界点 会进行返回
            // 当前head 是当前节点.也就是倒数第二个节点
            // head.next 是倒数第一个节点
            // head.next.next 是倒数第一个节点的指针 ，注意是指针 也就是个引用
            // 将倒数第一个节点 指向倒数第二个节点
            head.next.next = head; // 倒数第一个节点的指针 指向倒数第二个节点
            // 返回最后一个节点 ，链表逆置之后 最后一个节点就是新的链表 表头 我们进行返回
            // 这里也是递归到倒数第二个节点了
            return head.next;

        }
    }
}

class ListNodeA {
    int val;
    ListNodeB next = null;

    ListNodeA(int val) {
        this.val = val;
    }
}

